//1. 在数组中找到最大值出现的次数;


int MaxLenSize(vector<int>& nums)
{
    int n = nums.size();
    if(n == 1) return 1;

    int maxNum = nums[0], int count = 1;
    for(auto& i : nums)
    {
        if(maxNum < i)
        {
            maxNum = i;
            count = 1;
        }
        else if(maxNum == i)
        {
            count++;
        }
    }

    return count;
}


//2. 最长递增子序列的个数;
class Solution 
{
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        // 思考: len[i]为到达i位置结尾时的子序列, 最长递增子序列的长度;
        //  count[i]为到达i位置结尾时候的子序列, 最长递增子序列的个数;

        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);

        int retlen = 1, retcount = 1;
        // 先计算最长递增子序列的长度;
        for (int i = 1; i < n; i++) 
        {
            for (int j = i - 1; j >= 0; j--) 
            {
                if (nums[j] < nums[i]) 
                {
                    // 在判断len[i]和len[j] + 1;
                    if (len[j] + 1 == len[i]) 
                    {
                        //(1) == 的话刚好递增子数组的长度相同;
                        count[i] += count[j];
                    } 
                    else if (len[j] + 1 > len[i]) 
                    {
                        //(2) > 的话就是递增子数组长度要大  直接更新即可;
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                    //(3) < 的话直接无视;
                }
            }

            //如果len[i]最长递增子序列长度等于, 将出现个数相加;
            if(retlen == len[i])
            {
                retcount += count[i];
            }
            //len[i]最长递增子序列大于, 就更新;
            else if(retlen < len[i])
            {
                retlen = len[i];
                retcount = count[i];
            }
        }

        return retcount;
    }
};


//3. 最长数对链;
class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        int n = pairs.size();

        vector<int> dp(n ,1);
        sort(pairs.begin(), pairs.end());
        //dp[i]存放到达i位置的最大数对链;
        for(int i = 1; i < n; i++)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(pairs[j][1] < pairs[i][0])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        int ret = 0;
        for(auto& i : dp)
        {
            ret = max(ret, i);
        }

        return ret;
    }
};